Techniques for compressing data are common in the fields of communications and computers. In communications, it is often desirable to transmit compressed strings of data that upon reception can be reconstructed into their original form. Transmitting compressed data takes less time than transmitting the same data in an uncompressed format. In computers, compressed data offers a storage advantage over non-compressed data. Thus, for a storage device having a fixed storage capacity, more files can be stored therein if they are compressed.
Data compression techniques can be divided into two major categories: lossy and lossless. Lossless data compression techniques are employed when it is required that no information is lost in the compression/decompression process. Lossy data techniques are less accurate than lossless techniques but are generally are much faster. By definition, lossless compression techniques employ methods that guarantee the precise duplication of data after it has passed through the compression/decompression cycle. Lossless compression is most commonly associated with storage of digital data used in with a computer. Such applications include the storage of data base records, spread sheet information, and word processing files. If information in a data message is redundant so that its omission does not reduce, in any way, the information encoded in the data, the message can be shortened without losing any of the information encoded therein. Thus, lossless data compression reduces the size of the message without compromising the integrity of the information conveyed by the message.
Advanced driver assistance system (ADAS) algorithms as well as gaming, virtual reality, machine learning algorithms are all becoming limited by double data rate (DDR) memory performance and bandwidth. The data streams (radar data, images data, etc.) typically do show strong locality, but the bits are only “roughly equal”. Online data compression for raster data is needed to use DDR memory more effectively.
Compressing data is generally an easy problem to solve. The problems that are harder to solve are ensuring that the data size of the compressed data stream is bounded even for random data samples. Another problem is providing a decompression scheme during data read that is fast. Other problems include the requirement of being able to handle different data types and memory access schemes for such distinct data types. For example, a cache line fill versus a Direct Memory Access (DMA) controlled image data access will require different access schemes. Finally, another problem is providing random access to the compressed data within a deterministic and fixed time interval.